package sequence;

/**
 * @Author: LDeng
 * @Date: 2021-05-08 15:00
 */
public class KMP {


    public static int indexOf(String text, String pattern) {
        //前置判断
        if (text == null || pattern == null) return -1;
        char[] textChars = text.toCharArray();
        int tlen = textChars.length;
        if (tlen == 0) return -1;
        char[] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (plen == 0) return -1;
        if (tlen < plen) return -1;

        //next表
        int[] next=next(pattern);

        int pi = 0, ti = 0;
        int len=tlen-plen;
        while (pi < plen && ti-pi <= len) {
            if (textChars[ti] == patternChars[pi]) {
                ti++;
                pi++;
            } else {
                //查next表 ， 获取值赋值给pi
               pi=next[pi];
            }
        }
        return (pi==plen)?(ti-pi):-1;
    }

    //获取next表， 只需要提供模式串
    private static int[] next(String pattern){

        return null;
    }
}
